#include <stdio.h>

#include <iostream>
#define MAXSIZE 1000
using namespace std;
#include "../../head/myhead.h"

/**邻接矩阵:
 *  通过矩阵的形式存储图，由顶点列表和矩阵，两个结构体组成，
 */
typedef struct VertexType
{
    int no;    //顶点编号
    char info; //顶点元素所代表的值，一般不写
} VertexType;
typedef struct MatrixGraph
{
    VertexType adjVertex[MAXSIZE]; //顶点元素列表
    int nodeNums, edgeNums;        //顶点数量，边的数量
    int edge[MAXSIZE][MAXSIZE];
} MatrixGraph;

/**
 * 邻接表 由弧结点，顶点结点，邻接表三个结构体组成
 */
typedef struct ArcNode
{
    int adjvex;           //该边指向的结点的位置
    ArcNode *nextArcNode; //该结点的后继结点
    int info = -1;             //权值
} ArcNode;
//顶点，1.存储图的顶点信息，2.该顶点所指向的首个弧结点
typedef struct VNode
{
    char data;             //该顶点的数据
    ArcNode *firstArcNode; //该结点所指向的第一个弧结点（以弧结点形式存储）
} VNode;
//邻接表
typedef struct ArcGraph
{
    int nodeNums, edgeNums; //顶点数量，边的数量
    VNode adjList[MAXSIZE]; //图中所有结点的集合
} ArcGraph;

//见0.jpg
void createAGraph(ArcGraph *G)
{
    
    G->nodeNums = 5;
    G->edgeNums = 5;

    G->adjList[0].data = 'A';
    G->adjList[1].data = 'B';
    G->adjList[2].data = 'C';
    G->adjList[3].data = 'D';
    G->adjList[4].data = 'E';

    ArcNode *arcNode0 = (ArcNode *)malloc(sizeof(ArcNode));
    arcNode0->adjvex = 1;
    ArcNode *arcNode1 = (ArcNode *)malloc(sizeof(ArcNode));
    arcNode1->adjvex = 2;
    ArcNode *arcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
    arcNode2->adjvex = 3;
    ArcNode *arcNode3 = (ArcNode *)malloc(sizeof(ArcNode));
    arcNode3->adjvex = 3;
    ArcNode *arcNode4 = (ArcNode *)malloc(sizeof(ArcNode));
    arcNode4->adjvex = 4;

    G->adjList[0].firstArcNode = arcNode0;
    arcNode0->info = 1;
    arcNode0->nextArcNode = arcNode1;
    arcNode1->info = 1;
    arcNode1->nextArcNode = arcNode2;
    arcNode2->info = 1;
    arcNode2->nextArcNode = NULL;

    G->adjList[1].firstArcNode = NULL;

    G->adjList[2].firstArcNode = arcNode3;
    arcNode3->info = 1;
    arcNode3->nextArcNode = NULL;

    G->adjList[3].firstArcNode = arcNode4;
    arcNode4->info = 1;
    arcNode4->nextArcNode = NULL;

    G->adjList[4].firstArcNode = NULL;
}
void printAGraph(ArcGraph *G)
{
    for (int i = 0; i < G->nodeNums; i++)
    {
        ArcNode *p = G->adjList[i].firstArcNode;
        //遍历每个以数组元素为头结点的链表 以此来输出自己的边。
        while (p != NULL)
        {
            char node1 = G->adjList[i].data;
            char node2 = G->adjList[p->adjvex].data;
            cout<<"边( " << node1 << " , " << node2 << " )"
            << "的权值为" << p->info<<endl;
            p = p->nextArcNode;
        }
    }
}

/**
 * 深度优先遍历：参考二叉树先序遍历
 * 步骤：1.首先访问出发点v，并将其标记为已访问过
 *      2.取与v邻接的未被访问的任意一个顶点w，并访问它
 *      3.取与w邻接的未被访问过的顶点，如此重复
 *      4.如果当前顶点所有邻接顶点都被访问过了则退回最近被访问的顶点
*/
int visit[MAXSIZE];
void DFS(ArcGraph *g)
{
}

void BFS(ArcGraph *g)
{
}
int main()
{
    ArcGraph *G = (ArcGraph *)malloc(sizeof(ArcGraph));
    createAGraph(G);
    printAGraph(G);
    return 0;
}